{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.8.1-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python38164bitbed07143d37b49c8ba24bbf4d83c1753",
   "display_name": "Python 3.8.1 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from leetcode_test import TreeNode\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(\n",
    "        self, root: \"TreeNode\", p: \"TreeNode\", q: \"TreeNode\"\n",
    "    ) -> \"TreeNode\":\n",
    "        @lru_cache(None)\n",
    "        def find(root, value):\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val == value:\n",
    "                return True\n",
    "\n",
    "            return find(root.left, value) or find(root.right, value)\n",
    "\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if find(root, p.val) and find(root, q.val):\n",
    "                return root\n",
    "\n",
    "        return helper(root.left) or helper(root.right) or helper(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "想的很好，可惜是错的，如果找到了，还需要判断他的子节点是不是也能找到"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def lowestCommonAncestor(\n",
    "        self, root: \"TreeNode\", p: \"TreeNode\", q: \"TreeNode\"\n",
    "    ) -> \"TreeNode\":\n",
    "        @lru_cache(None)\n",
    "        def find(root, value):\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val == value:\n",
    "                return True\n",
    "\n",
    "            return find(root.left, value) or find(root.right, value)\n",
    "\n",
    "        def helper(root):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            if find(root.left, p.val) and find(root.left, q.val):\n",
    "                return helper(root.left)\n",
    "            elif find(root.right, q.val) and find(root.right, p.val):\n",
    "                return helper(root.right)\n",
    "            else:\n",
    "                return root\n",
    "\n",
    "        return helper(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}